#ifndef LEETCODE_LIST_H
#define LEETCODE_LIST_H

#include <iostream>
#include <list>
#include <functional>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};


class MyLinkedList {
private:

    ListNode* head;

public:
    MyLinkedList() {
        head = new ListNode;
    }

    int get(int index) {
        ListNode* node = head->next;
        while(node && index > 0) {
            node = node->next;
            index--;
        }
        return node ? node->val : -1;
    }

    void addAtHead(int val) {
        ListNode* new_head = new ListNode(val);
        new_head->next = head->next;
        head->next = new_head;
    }

    void addAtTail(int val) {
        ListNode* tail = head;
        while(tail->next) {
            tail = tail->next;
        }
        tail->next = new ListNode(val);
    }

    void addAtIndex(int index, int val) {
        ListNode* node = head;
        while(index > 0 && node->next) {
            node = node->next;
            index--;
        }
        if(node == head && index > 0) return;
        if(node && node->next) {
            ListNode* tmp = node->next;
            node->next = new ListNode(val);
            node->next->next = tmp;
        } else if(node) {
            node->next = new ListNode(val);
        } else {
            return;
        }

    }

    void deleteAtIndex(int index) {
        ListNode* node = head;
        while(node && index > 0) {
            node = node->next;
            index--;
        }
        if(node && node->next) {
            ListNode* tmp = node->next;
            node->next = node->next->next;
            delete tmp;
        }
        return;
    }

    ListNode* &real_head() { return head->next; }
    ListNode* dummy_head() { return head; }

    void print_list() {
        ListNode* node = head->next;
        while(node) {
            std::cout << node->val << std::endl;
            node = node->next;
        }
    }

};

/**************************************************************/
template<class T>
void print_list(std::list<T> li, int n) {
    for(const auto &elem : li) {
        std::cout << elem << std::endl;
        if(--n == 0) return;
    }
}

template<class T>
void print_list(std::list<T> li) {
    for(const auto &elem : li) {
        std::cout << elem << std::endl;
    }
}

void print_list(ListNode* head) {
    while(head) {
        std::cout << head->val << std::endl;
        head = head->next;
    }
}

/****************************************************************/

//! 206. 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* cur_head = head;
    ListNode* cur_node = head;
    while (cur_node->next) {
        ListNode* tmp = cur_node->next->next;
        cur_node->next->next = cur_head;
        cur_head = cur_node->next;
        cur_node->next = tmp;
    }
    return cur_head;
}

//! 203.移除链表元素
ListNode* removeElements(ListNode* head, int val) {
    while(head && head->val == val) {
        head = head->next;
    }
    ListNode* node = head;
    while(node && node->next) {
        if(node->next->val == val) {
            node->next = node->next->next;
            node = node->next;
        }
    }
    return head;
}

//! 24. 两两交换链表中的节点
ListNode* swapPairs(ListNode* head) {
    ListNode null_head(0, head);
    ListNode* cur_node = head;
    ListNode* prev_node = &null_head;
    while (cur_node && cur_node->next) {
        ListNode* tmp = cur_node->next->next;
        cur_node->next->next = cur_node;
        prev_node->next = cur_node->next;
        cur_node->next = tmp;
        prev_node = cur_node;
        cur_node = tmp;
    }
    return null_head.next;
}

//! 19. 删除链表的倒数第 N 个结点
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* node = head;
    for(int i=0; i<n; i++) {
        node = node->next;
        if(!node) return head->next;
    }
    ListNode* res_node = head;
    while (node->next) {
        node = node->next;
        res_node = res_node->next;
    }
    ListNode* tmp = res_node->next;
    res_node->next = res_node->next->next;
    delete tmp;
    return head;
}

//! 160.链表相交
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(!headA || !headB) return nullptr;
    ListNode* nodeA = headA;
    ListNode* nodeB = headB;
    int lenA = 0, lenB = 0;
    while(nodeA->next) {
        nodeA = nodeA->next;
        lenA++;
    }
    while(nodeB->next) {
        nodeB = nodeB->next;
        lenB++;
    }
    if(nodeA != nodeB) return nullptr;
    nodeA = headA;
    nodeB = headB;
    if(lenA > lenB) {
        for(int i=0; i<(lenA - lenB); i++) {
            nodeA = nodeA->next;
        }
    } else {
        for(int i=0; i<(lenB - lenA); i++) {
            nodeB = nodeB->next;
        }
    }
    while (nodeA != nodeB) {
        nodeA = nodeA->next;
        nodeB = nodeB->next;
    }
    return nodeA;
}

//! 142.环形链表II
ListNode *detectCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow) {
            slow = head;
            while (fast != slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    }
    return nullptr;
}

void reorderList(ListNode* head) {
    function<ListNode*(ListNode*)> reverse = [](ListNode* head){
        ListNode* cur_head = head;
        ListNode* cur_node = head;
        while (cur_node && cur_node->next) {
            ListNode* tmp = cur_node->next->next;
            cur_node->next->next = cur_head;
            cur_head = cur_node->next;
            cur_node->next = tmp;
        }
        return cur_head;
    };

    ListNode* fast = head, *slow = head, *right, *node;
    while(fast && fast->next) {
        node = slow;
        fast = fast->next->next;
        slow = slow->next;
    }
    if(fast) {
        right = reverse(slow->next);
        slow->next = nullptr;
    } else {
        right = reverse(slow);
        node->next = nullptr;
    }
    node = head;
    while(right) {
        ListNode* node_next = node->next;
        ListNode* right_next = right->next;
        node->next = right;
        right->next = node_next;
        right = right_next;
        node = node_next;
    }

    right = nullptr;
    return;
}
#endif